/*
https://leetcode-cn.com/problems/form-largest-integer-with-digits-that-add-up-to-target/solution/shu-wei-cheng-ben-he-wei-mu-biao-zhi-de-dnh86/
 */
import java.util.Arrays;

public class Solution1449 {
    public String largestNumber(int[] cost, int target) {
        int[][] f=new int[target+5][11];
        int[] map=new int[target+5];
        map[0]=1;
        for (int i=1;i<=9;i++){
            for (int j=0;j<=target;j++){
                if (j-cost[i-1]>=0 && map[j-cost[i-1]]==1){
                    int[] n=Arrays.copyOf(f[j-cost[i-1]],11);
                    n[i]=n[i]+1;
                    n[10]=n[10]+1;
                    if (map[j]==0 || compare(n,f[j],i)>0){
                        f[j]=n;
                        map[j]=1;
                    }
                }
            }
        }
        if (map[target]==0){
            return "0";
        }else{
            int[] n=f[target];
            StringBuilder stringBuilder=new StringBuilder();
            for (int i=9;i>=1;i--){
                for (int j=0;j<n[i];j++){
                    stringBuilder.append(i);
                }
            }
            return stringBuilder.toString();
        }
    }

    int compare(int[] a,int[] b,int pos){
        if (a[10]!=b[10]){
            return a[10]-b[10];
        }else{
            for (int i=pos;i>=1;i--){
                if (a[i]!=b[i]){
                    return a[i]-b[i];
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1449().largestNumber(new int[]{1,1,1,1,1,1,1,1,1},5000));
    }
}
